Obeleži sve kategorije koje odgovaraju problemu

Једнодимензионалне колекције података

Елементи програмског језика

Најједноставнија колекција која се може користити за истовремено складиштење целе серије података је класичан низ.

Статички алоцирани низови

У језику C++ величина класичних статичких низова мора бити позната у фази превођења програма и зато је потребно унапред знати њихов максимални број елемената. У такмичарским задацима ово је обично саставни део формулације задатка, међутим, у реалној програмерској пракси оваква ограничења често или нису позната или су доста већа од броја елемената које програм обично користи тако да се меморија непотребно заузима. Статички низови у језику C++ се обично користе на следећи начин.

const int MAX = 50000;
int a[MAX];
int n;
cin >> n;
for (int i = 0; i < n; i++)
  cin >> a[i];
...

Приметимо да је MAX константа која је позната у време превођења програма.

Постоји значајна разлика између статички алоцираних низова који су декларисани унутар функција (локално) и оних декларисаних ван свих функција (глобално). Глобални низови обично могу бити знатно већи и вредности свих елемената су иницијално постављене на нулу (код локалних низова иницијалне вредности елемената нису дефинисане).

Димензија статички алоцираног низа (максимални број елемената) често је већа од стварног броја елемената уписаних у низ. Стога је увек потребно у посебној променљивој памтити колико елемената низ стварно садржи (у наведеном примеру то је била променљива n). Приликом преноса низа у функцију, потребно је уз низ проследити и ту променљиву.

Функције којима су низови параметри примају само меморијску адресу почетка низа. Све модификације низа унутар функције врше се над оригиналним низом (оним који је наведен као аргумент, приликом позива). Стога су низови увек улазно-излазни параметри функција (за разлику од, на пример, података типа int или структура који су улазни параметри, осим ако се не проследе по референци). Статички низови који су дефинисани у функцијама се ослобађају по завршетку извршавања тела функције и није их могуће вратити као резултујућу вредност функције (ако функција треба да врати статички низ, њега је неопходно проследити као параметар функције и функција може само да попуни његове елементе).

VLA

Неки компилатори подржавају облик низова који се назива VLA (engl. variable length array), где се као димензија низа наводи променљива чија је вредност позната тек у фази извршавања програма.

int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
  cin >> a[i];
...

VLA никада нису били део стандарда језика C++ (једно време били су део стандарда језика C, па су након тога избачени) и стога их никако није препоручљиво користити.

Динамички алоцирани низови

Алокација низова у језику C++ у тренутку извршавања програма (тзв. динамичка алокација) је могућа (оператором new), али захтева рад са показивачима и ручно ослобађање меморије (оператором delete []) и сматра се прилично напредном темом, тако да ту врсту низова нећемо користити.

int n;
cin >> n;
int *a = new int[n];
for (int i = 0; i < n; i++)
  cin >> a[i];
...
delete[] a;

У језику C++ за динамичку алокацију низова могуће је користити и библиотеку за рад са меморијом језика C и функције malloc и free, међутим и тај облик рада са низовима је непримерен језику C++ и препоручујемо да се у њему не користи.

int n;
cin >> n;
int *a = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
  cin >> a[i];
...
free(a);

Библиотечке колекције (vector, array)

Најбоље решење долази у форми динамички алоцираних библиотечких колекција тј. колекција за чије се складиштење меморија заузима тек током извршавања (а не током превођења) програма и које програмеру пружају веома удобан интерфејс за рад са динамички алоцираном меморијом. У језику C++ најчешће коришћена динамичка колекција, која одмењује класичне, статички алоциране низове је вектор (vector из заглавља <vector>).

• Вектор је параметризован типом елемената које чува тако да се користе vector<int>, vector<double>, vector<string>, али и, на пример, vector<vector<int>>.
• Ако је број елемената вектора n познат пре његове декларације (а у току извршавања програма), тада је вектор најбоље декларисати уз навођење димензије у склопу декларације (на пример, vector<double> a(n)). Могуће је навести и почетну вредност свих елемената (на пример, декларацијом vector<double> a(n, 1.0) гради се вектор од n елемената постављених на вредност 1.0).
• Након декларације у којој је наведен број елемената, вектор се користи на потпуно исти начин као и низ (елементу на позицији i приступа се са a[i]). Димензију (број елемената) вектора a можемо одредити помоћу методе a.size() (метода је посебан облик функције која се позива над неким објектом тако што се име тог објекта наводи испред имена функције и тачкице и која нам даје неке информације о том објекту или проузрокује одређене измене тог објекта).
• Једна од најзначајнијих предности вектора у односу на класичне низове је то што им се димензија може мењати током извршавања програма. Проширивање вектора a додавањем елемента x на његов крај могуће је уз помоћ позива методе a.push_back(x) (тиме се увећава број елемената за 1).
• Промена димензије вектора се може урадити методом resize - након позива a.resize(n) вектор a има димензију n (под условом да је било довољно меморије).
• Простор за смештање елемената у вектор можемо резервисати и без промене његове димензије коришћењем методе reserve. Након позива a.reserve(n) резервише се простор за смештање n елемената, али величина вектора остаје непромењена (у почетку 0), све док се елементи не додају помоћу push_back.

Најчешћи облик коришћења вектора у овој збирци је следећи.

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
  cin >> a[i];
...

Ако број елемената није задат у посебној променљивој, могуће је очитати га методом size.

for (int i = 0; i < a.size(); i++)
  // obradjuje se a[i]

Савремени C++ (почевши од стандарда C++-11) допушта и краћи облик петље којом се обрађује један по један елемент вектора (али и низа и других библиотечких колекција). У многим језицима оваква петља назива се петља foreach.

for (int x : a)
  ...

Вектори се у функције преносе по вредности (осим ако се експлицитно не наведе да се преносе по референци), што значи да се у функцију преноси копија вектора који је наведен као аргумент у позиву. Ако желимо да функција модификује садржај вектора, неопходно га је пренети по референци (навођењем симбола &). Тада се у функцију шаље само меморијска адреса тог вектора и све операције се спроводе над оригиналним вектором (не врши се копирање). Копирањем се непотребно троши меморија и време, па има смисла векторе проследити по референци и функцијама које само анализирају њихов садржај и не мењају их. Тада се обично наводи кључна реч const чиме се обезбеђује да се вектор не може променити у функцији иако је пренет по референци. На пример,

int zbir(const vector<int>& a) {
   int z = 0;
   for (int x : a)
      z += a;
   return z;
}

Функција може да врати вектор као своју резултујућу вредност. Захваљујући тзв. семантици премештања (енгл. move semantics) уведеној у савременим верзијама језика C++ не врши се никакво копирање садржаја, па се овим не умањују перформансе програма.

Рецимо и да у језику C++, од стандарда C++-11 постоји колекција array која је веома слична класичном статичком низу (фиксне је величине и та величина се наводи у оквиру типа), међутим, нуди одређене методе и глобалне функције које омогућавају да се добије колекција која има ефикасност класичних низова, а удобност коришћења вектора (на пример, величину увек можемо сазнати методом size, док код обичних низова пренетих у функцију немамо могућност да сазнамо величину, већ је морамо прослеђивати као параметар функције). Ипак, у овој збирци array нећемо користити.

const int MAX = 100;
array<int, MAX> a;
for (int i = 0; i < n; i++)
  cin >> a[i];
...

Једнодимензионалне колекције података

Елементи програмског језика

Класични низови

Најједноставнија колекција која се може користити за истовремено складиштење целе серије података је класичан низ.

У језику C# класични низови су динамички алоцирани (димензија низа се може задати и меморија се може заузети приликом креирања низа у фази извршавања програма). Најчешћи облик рада са низовима је следећи:

// ucitavamo broj elemenata niza
int n = int.Parse(Console.ReadLine());
// alociramo memoriju za smestanje n elemenata niza
int[] a = new int[n];
// ucitavamo jedan po jedan element niza
for (int i = 0; i < n; i++)
    a[i] = int.Parse(Console.ReadLine());
...

Тип int[] означава низ података типа int. Могуће је правити низове елемената било ког типа, али сви елементи у једном низу морају имати исти тип. Оператором new врши се алокација (заузимање меморије) низа и у том тренутку је неопходно навести дужину низа тј. број потребних елемената. Захваљујући сакупљачу отпадака језика C#, програмер не мора да води рачуна о деалокацији (ослобађању меморије, када нам подаци из низа више нису потребни).

Елементу низа a на позицији i могуће је приступити помоћу a[i], при чему бројање позиција (каже се и индекса) креће од нуле.

Алоциран низ се на даље не може проширивати, тј. није му могуће додавати елементе (једино је могуће очитавати и мењати вредности елемената).

Листе

Пошто је у многим задацима потребно складиштење серија података чија величина није унапред позната, пожељно је користити колекције које имају могућност аутоматског проширивања додавањем података на крај. У језику C# таква колекција је листа (њу не треба мешати са повезаним листама о којима ће речи бити у другом тому ове збирке) која се представља типом података List<T> који је део библиотеке System.Collections.Generic. Ово је генерички тип података, што значи да се уместо T наводи конкретан тип елемената листе. Тако ћемо за складиштење целих бројева користити List<int>, за складиштење реалних бројева List<double> и слично. Листе се конструишу оператором new. Пошто се тип листе наводи иза речи new приликом декларације променљиве могуће је употребити и кључну реч var којом се компилатору налаже да сам закључи тип променљиве на основу типа вредности којом се она иницијализује. Приликом конструкције је могуће навести очекивани капацитет - листа остаје празна, а елементи се додају методом¹ Add.

Приступ елементима листе врши се на исти начин као и приступ елементима низова (елементу листе a на позицији i приступа се помоћу a[i], при чему се позиције броје од нуле).

У следећем примеру креирамо листу и попуњавамо их учитаним бројевима, све док се не учита нула.

// kreiramo praznu listu
var a = new List<int>();
while (true)
{
    // ucitavamo element i ako je ucitana nula prekidmo ucitavanje
    int x = int.Parse(Console.ReadLine();
    if (x == 0) break;
    // u suprotnom listu prosirujemo ucitanim elementom
    a.Add(x);
}

Ако је број елемената познат пре декларације, а елементи неће бити додавани накнадно, уместо листе боље је користити класичан, динамички алоциран низ (низ типа int[]), јер је он бржи и захтева мало мање меморије.

Често је потребно у петљи проћи кроз све елементе неке колекције. То је могуће урадити петљом у којој се индекси крећу од нуле па до броја елемената. Ако је у питању низ број елемената се може одредити својством² Length.

int[] a;
...
for (int i = 0; i < a.Length; i++)
  // obradjuje se a[i]

Ако је у питању листа број елемената се може одредити својством Count.

List<int> a;
...
for (int i = 0; i < a.Count; i++)
  // obradjuje se a[i]

Краћи и елегантнији начин да се обраде сви елементи колекције је да се употреби петља foreach, која се на исти начин употребљава без обзира да ли је у питању низ или листа (касније ћемо видети да се она може употребити за све набројиве колекције, тј. све колекције које имплементирају интерфејс IEnumerable).

foreach (int x in a)
  ...

За разлику од бројева, логичких вредности, структура и слично који су вредносни типови, низови и листе су референтни типови. Наиме, и низови и листе су заправо променљиве у којима се чувају меморијске адресе на којима се налазе сами елементи. Ако доделимо низ низу или листу листи, ми заправо стварамо нову променљиву која садржи исту адресу, тако да једном те истом низу приступамо помоћу два имена (што обично није оно што желимо). Да би се заиста креирао нови низ или нова листа потребно је обавезно навести кључну реч new и извршити алокацију меморије.

Када се низ или листа шаљу у функцију, тада до функције долази копија меморијске адресе на којој се налази елементи, што за последицу има да низ који је параметар функције указује на исте елементе као и низ који је наведен као аргумент позива. Зато је у функцијама могуће мењати садржај низова и свака промена елемената низа направљена у функцији ће се заиста осликати на низ који је функцији прослеђен. Са друге стране, ако у функцији желимо да креирамо нови низ (да се унутар функције изврши алокација оператором new), тада тај низ из функције морамо вратити или преко повратне вредности функције (наредбом return) или преко повратног (out) параметра. Ситуација са листама је потпуно аналогна.